package com.captain.special.二叉树.简单;

import com.captain.leetcode.TreeNode;

/**
 * Des:
 * TODO ******
 * @author XL
 * @Date 2022/5/8 15:51
 */
public class 另一棵树的子树572 {
    boolean flag = false;
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        return recur(root, subRoot);
    }

    public boolean recur(TreeNode root, TreeNode subRoot) {
        if (root == null) {
            return false;
        }
        //如果有成功的了,则无需再寻找
        if(flag) {
            return true;
        }
        //比较当前节点是否满足
        boolean check = check(root, subRoot);
        flag = check;
        boolean left = recur(root.left, subRoot);
        boolean right = recur(root.right, subRoot);
        //只要有一个成功,则成功
        return check || left || right;
    }

    public boolean check(TreeNode r, TreeNode s) {
        if (r == null && s == null) {
            return true;
        }
        if (r == null || s == null || r.val != s.val) {
            return false;
        }
        return check(r.left, s.left) && check(r.right, s.right);
    }
}
